1. Field of the Invention
The present invention relates generally to a general-purpose genetic algorithm machine for executing genetic algorithms and more particularly to a hardware framework for accelerating the execution speed of a genetic algorithm. The present invention is also directed to a method for producing the general-purpose genetic algorithm machine and further to a method for executing a genetic algorithm.
2. Description of the Related Art
FIG. 25 shows a conceptual diagram of a conventional genetic algorithm.
Generic algorithms (hereinafter referred to by the initials, GA) were introduced in 1975 by John Holland as a method for finding an optimum solution to complicated problems. (John H. Holland, "Adaptation in Natural and Artificial Systems," University of Michigan Press, 1975; Second edition: MIT Press, 1992.) For example, the GA is a useful method for finding optimum solutions to the Traveling Salesman Problem described by Grefenstette. In the GA, an emulated chromosomal data structure is initially designed to represent a candidate or trial solution. A plurality of n-bit chromosomes of that data structure are then randomly generated. A plurality of generated chromosomes are registered in groups or populations. A plurality of parent chromosomes are selected from this population of generated chromosomes according to a given algorithm. Each generated chromosome is assigned a unique problem-specific fitness which differs from other chromosomes in the population identifying a solution quality of the chromosome. The problem-specific fitness is expressed by a fitness value. Chromosomes are selected from the population of chromosomes in proportion to their fitness values with more-fit chromosomes having higher probability of being selected. When a pair of parent chromosomes are selected from the population, the parent chromosomes are combined with a probabilistically generated cutpoint. In the case of having no cutpoint generated, either of the parent chromosomes is simply copied to provide a new chromosome as a child chromosome. Thus, a child chromosome is created and outputted. The child chromosome therefore contains portions of each parent or the whole portion of a parent. The child chromosome is then mutated. The mutation is performed with a low probability. The mutation is performed through inversion of a bit in the child chromosome. A mutated child chromosome is then evaluated to be assigned its fitness value. An evaluated child chromosome along with its fitness value is stored as a member of the next generation in the population.
After repeated iteration of this process, the general fitness of chromosomes in the population improves. Thus, a solution to the problem emerges in the population. A solution to the problem is acquired with highly fit chromosomes concentrated in the population.
A major disadvantage of the conventional GA is that the GA is extremely slow in its execution speed when emulated by software on a conventional general-purpose computer.
Some proposals have been addressed for accelerating the processing speed of a GA. Graham, et al. has proposed a hardware implementation of the GA using the Splash 2 machine (Paul Graham and Brent Nelson, "A Hardware Genetic Algorithm for the Traveling Salesman Problem on Splash 2" Field-Programmable Logic and Applications, ed. W. More and W. Luk, pp. 352-361, Springer, Oxford, 1995). A similar attempt of hardware implementation of a GA to accelerate the execution speed of the GA has been proposed by Sitkoff et al. (Nathan Sitkoff, Mike Wazlowski, Aaron Smith, and Harvey Silverman, "Implementing a Genetic Algorithm on a Parallel Custom Computing Machine, " Proceedings of IEEE Workshop on FPGAs for Custom Computing Machines, pp. 180-187, 1995).
These attempts of the hardware implementation of a GA, however, ended in limited success with the speedup factors of roughly 10 times. One reason for their limited gains is copying the original GA proposed by Holland to be implemented on hardware. The original GA into the hardware implementation has thus inefficiencies introduced therein.
Another reason that greater speed gains are not realized is the underlying hardware architecture being used to implement the GA. Graham, et al. employs the Splash 2 machine which is a reconfigurable computer designed to support linear systolic data such as SIMD (single instruction, multiple data) and MIMD (multiple instruction, multiple data).
Sitkoff, et al. employs the Armstrong 3 machine which is a loosely-coupled MIMD multicomputer with reconfigurable computing capabilities. They achieved only limited gains because they implemented GAs in machines whose hardware architectures are not designed originally or particularly to implement the GAs. This can prevent the execution speed of GAs from achieving satisfactory gains.
Thus, a major drawback of conventional machines is the slow execution speed of a GA when emulated by software on conventional general-purpose computers.
A hardware-based implementation of a GA has been addressed for offsetting the drawback but only with a limited success in its execution speed.